package com.example.algorithm.sort.merge;

import com.example.algorithm.sort.BaseSort;

/**
 * @program: algorithm
 * @description:
 * @packagename: com.example.algorithm.sort.merge
 * @author: Jay
 * @date: 2022/03/26 18:42:03
 **/
public class Merge extends BaseSort {
    //归并所需要的辅助数组
    private static Comparable[] assist;

    /**
     * 对数组a进行排序
     * @param a
     */
    public static void sort(Comparable[] a){
        //1.初始化辅助数组assist
        assist = new Comparable[a.length];
        //2.定义lo变量，和hi变量，分别记录数组中最小的索引和最大的索引
        int lo = 0;
        int hi = a.length-1;
        //3.调用sort重载方法完成数组a中，从索引lo到所有hi的元素的排序
        sort(a,lo,hi);
    }

    /**
     * 对数组a中的lo到hi的元素进行排序
     * @param a
     * @param lo
     * @param hi
     */
    public static void sort(Comparable[] a, int lo, int hi){
        //安全性校验
        if (hi <= lo){
            return;
        }
        //对lo到hi之间的数据进行分两个组
        int mid = lo + (hi - lo)/2;
        //分别对每一组数据进行排序
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        //再把两个组数据进行归并
        merge(a,lo,mid,hi);
    }

    /**
     * 对数组中，从lo到mid为一组，mid+1到hi为一组，将两组数据进行归并
     * @param a
     * @param lo
     * @param mid
     * @param hi
     */
    public static void merge(Comparable[] a, int lo, int mid, int hi){
        //定义三个指针
        int i = lo;
        int p1 = lo;
        int p2 = mid+1;

        //遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组对应的索引
        while (p1 <= mid && p2 <= hi){
            //比较对应索引处的值
            if (less(a[p1],a[p2])){
                assist[i++] = a[p1++];
            }else {
                assist[i++] = a[p2++];
            }
        }
        //遍历，如果p1的指针没走完，那么顺序移动p1指针，把对应的元素放到辅助索引的对应数组中
        while (p1 <= mid){
            assist[i++] = a[p1++];
        }

        //遍历，如果p2的指针没走完，那么顺序移动p2指针，把对应的元素放到辅助索引的对应数组中
        while (p2 <= hi){
            assist[i++] = a[p2++];
        }

        //把辅助数组的元素拷贝到原数组中
        for (int index = lo;index <= hi;index++){
            a[index] = assist[index];
        }

    }

}
